package leetcode1;

public class Day2 {

    public static void main(String[] args) {

    }
    //647.最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        int ret = 1,i=0;
        for(int j=1;j<nums.length;j++) {
            if(nums[j] <= nums[j-1]) i=j;
            else ret = Math.max(ret,j-i+1);
        }
        return ret;
    }


    //121.买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int preMinV = Integer.MAX_VALUE;
        int ret = 0;
        for(int i=0;i<prices.length;i++) {
            preMinV = Math.min(preMinV,prices[i]);
            ret = Math.max(ret,prices[i]-preMinV);
        }
        return ret;
    }


    //115.不同的子序列
    public int numDistinct(String s, String t) {
        int m = t.length(),n = s.length();
        int[][] dp = new int[m+1][n+1];
        //dp[i][j]：在s的[0,j]区间的子序列中，有多少个t的[0,i]个子串
        for(int i=0;i<n;i++) dp[0][i]=1; //初始化第一行
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(s.charAt(j) == t.charAt(i)) dp[i+1][j+1]=dp[i][j];
                dp[i+1][j+1] += dp[i+1][j];
            }
        }
        return dp[m][n];
    }


}
